package top.truism.sword;

/**
 * 找出环形链表上的入口节点
 */
public class FindNodeInLoop {

    /**
     * 找出环形链表上的入口节点
     * @param head
     * @return
     */
    public RemoveDuplicateNode.ListNode listNodeInLoopList(RemoveDuplicateNode.ListNode head) {

        RemoveDuplicateNode.ListNode slow = head;
        RemoveDuplicateNode.ListNode fast = head;
        boolean foundNode = false;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                foundNode = true;
                break;
            }
        }
        if(!foundNode) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

}
